package suanfa.linklist.第六章.第一节;

public class TestBinarySearch {

    public static boolean isPower(int n){
        //先定义最小值、最大值
        int low=1;
        int high=n;

        int mid;
        /*
        //相当于是个中间值（临时值），保存中间那个数的平方，和n作比较，
        比如n=15，mid就是8,8*8=64,既然中位数8的平方都大于n，那么8后面的数肯定更大于n了，当然就不用考虑8后面的数了

        那现在high就变成了8，mid就是4，4*4=16，既然中位数4的平方都大于n，那么4后面的数肯定更大于n了，当然就不用考虑4后面的数了

        那现在high就变成了4，mid就是2，2*2=4，既然中位数2的平方都小于n，那么2之前的数肯定更小于n了，当然就不用考虑2前面的数了
         */
        int power;

        while(low<high){

            mid=(low+high)/2;

            power=mid*mid;

            if(power>n){
                high=mid-1;
            }else if(power<n){
                low=mid+1;
            }else{
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int n1=1000000;
        int n2=10000000;
        if(isPower(n1)){
            System.out.println(n1+"是某个数的自然数");
        }else {
            System.out.println(n1+"不是某个数的自然数");
        }

        if(isPower(n2)){
            System.out.println(n2+"是某个数的自然数");
        }else {
            System.out.println(n2+"不是某个数的自然数");
        }
    }
}
